1117C - Magic Ship - CodeForces Solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <tuple>
#include <cmath>
#include <sstream>
#include <bitset>
#include <list>
#include <cstring>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tiii;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<ld> vd;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<vb> vvb;
typedef vector<vc> vvc;
typedef vector<vs> vvs;
typedef vector<pii> vpii;
typedef vector<tiii> vtiii;

#define test int tt; scanf("%d", &tt); while (tt--)
#define forn(i, r) for (int (i) = 0; (i) < (r); ++(i))
#define loop(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
#define ep emplace_back
#define ff first 
#define ss second
#define all(x) (x).begin(), (x).end()
#define len(x) (int)(x).size()
#define UNIQUE(x) (x).resize(unique(all(x))-(x).begin())
#define LSOne(S) (S & (-S))

#define oo (int)1e9
#define ooo (ll)1e18

void fast() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
}

map<char, int> idx = {{'U', 0}, {'D', 1}, {'R', 2}, {'L', 3}};

vl dir_x = {0, 0, 1, -1};
vl dir_y = {1, -1, 0, 0};

ll sx, sy, tx, ty, n;
string s;
vl dx, dy;

bool f(ll k) {
    ll x = sx, y = sy;
    
    ll c = k / n, r = k % n;
    x += c * dx[n] + dx[r];
    y += c * dy[n] + dy[r];
    
    return abs(x-tx) + abs(y-ty) <= k;
}

int main() {
    cin >> sx >> sy >> tx >> ty >> n >> s;
    
    dx.resize(n+1, 0);
    dy.resize(n+1, 0);
    
    for (int i = 0; i < n; i++) {
        dx[i+1] = dx[i] + dir_x[idx[s[i]]];
        dy[i+1] = dy[i] + dir_y[idx[s[i]]];
    }
    
    ll l = 0, r = (ll)1e18;
    
    while (r - l > 1) {
        ll mid = l + (r - l) / 2;
        if (f(mid)) r = mid;
        else l = mid;
    }
    
    if (f(r)) cout << r << endl;
    else cout << -1 << endl;
    
    return 0;
}